package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.*;

public class _126_danci_jielong {
    
    static class bfs {
        
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            Set<String> words = new HashSet<>(wordList);
            words.remove(beginWord);
            Map<String, List<String>> paths = new HashMap<>();
            Map<String, Integer> steps = new HashMap<>();
            steps.put(beginWord, 0);
            LinkedList<String> q = new LinkedList<>();
            q.offer(beginWord);
            int step = 1;
            boolean found = false;
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    String cur = q.poll();
                    char[] arr = cur.toCharArray();
                    int len = arr.length;
                    for (int j = 0; j < len; j++) {
                        char c = arr[j];
                        for (char k = 'a'; k <= 'z' ; k++) {
                            arr[j] = k;
                            String newWord = new String(arr);
                            if (steps.containsKey(newWord) && step == steps.get(newWord))
                                paths.get(newWord).add(cur);
                            if (!words.contains(newWord))
                                continue;
                            words.remove(newWord);
                            steps.put(newWord, step);
                            paths.computeIfAbsent(newWord, $ -> new ArrayList<>()).add(cur);
                            q.offer(newWord);
                            if (newWord.equals(endWord))
                                found = true;
                        }
                        arr[j] = c;
                    }
                }
                step++;
                if (found)
                    break;
            }
            List<List<String>> res = new ArrayList<>();
            if (found) {
                Deque<String> path = new ArrayDeque<>();
                path.add(endWord);
                backtrack(res, path, paths, endWord, beginWord);
            }
            return res;
        }
        
        void backtrack(List<List<String>> res, Deque<String> q, Map<String, List<String>> paths, String cur, String beginWord) {
            if (cur.equals(beginWord)) {
                res.add(new ArrayList<>(q));
            } else {
                for (String s : paths.get(cur)) {
                    q.addFirst(s);
                    backtrack(res, q, paths, s, beginWord);
                    q.removeFirst();
                }
            }
        }
    }
}
